package com.leetcode.August;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description: 146. LRU 缓存
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-28 16:31
 */
public class LC146LRU缓存 {
    private static class Node {
        int key, value;
        Node next, prev;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Node dummy = new Node(0, 0); // 哨兵节点
    private final Map<Integer, Node> keyToNode = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
        //初始化双向循环链表
/**
 * 新加入的元素可以轻松地插入到链表的头部，
 * 而最久未访问的元素则位于链表的尾部，便于在缓存满时快速移除
 * */
    }

    //抽出一本书
    private void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }

    //放在最上面
    private void pushFront(Node x) {
        x.prev = dummy;
        x.next = dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }

    private Node getNode(int key) {
        if (!keyToNode.containsKey(key)) { // 没有这本书
            return null;
        }
        Node node = keyToNode.get(key); // 有这本书
        remove(node); // 把这本书抽出来
        pushFront(node); // 放在最上面
        return node;
    }


    public int get(int key) {
        Node node = getNode(key);
        return node == null ? -1 : node.value;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        if (node != null) {
            node.value = value;
            return;
        }
        node = new Node(key, value);
        keyToNode.put(key, node);
        pushFront(node);
        if (keyToNode.size() > capacity) {
            Node last = dummy.prev;
            remove(last);
            keyToNode.remove(last.key);
        }
    }
}
